package com.zpself.module.算法练习.计算;

import java.util.*;

/**
 * @author By ZengPeng
 * @Description 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
 * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
 *
 * 示例 1：
 * 输入：[1, 2, 2, 3, 1]
 * 输出：2
 * 解释：
 * 输入数组的度是2，因为元素1和2的出现频数最大，均为2.
 * 连续子数组里面拥有相同度的有如下所示:
 * [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
 * 最短连续子数组[2, 2]的长度为2，所以返回2.
 *
 * @date in  2021/2/20 9:17
 * @Modified By
 */
public class 力扣_697_数组的度 {

    public static void main(String[] args) {
        System.out.println(findShortestSubArray(new int[]{1, 2, 2, 3, 1}));
    }

    //题解：hash存储每个数出  信息 int【次数、开始位置、结束位置】
    public static int findShortestSubArray(int[] nums) {
        //1.求出最大值
        Map<Integer,int[]> map  =new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
           if(map.containsKey(nums[i])){
               map.get(nums[i])[0]++;
               map.get(nums[i])[2] = i;
           }else {
               map.put(nums[i],new int[]{1,i,i});
           }
        }
        //2.找出最大值的坐标差值
        int max=0,len=0;
        for (Map.Entry<Integer,int[]> mapEntry : map.entrySet()) {
            int[] arr = mapEntry.getValue();
            if(arr[0]>max){
                len = arr[2]-arr[1]+1;
                max = arr[0];
            }else if(arr[0]==max){
                len = len < (arr[2]-arr[1]+1) ? len : (arr[2]-arr[1]+1);
            }
        }
        return len;
    }
}
